﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int N = 1010;
int n, V,v[N],w[N];
int dp[N][N];
int main()
{
	// 读⼊数据
	cin >> n >> V;
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];
	// 搞定第⼀问
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= V; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= v[i])
				dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
		}
	}
	cout << dp[n][V] << endl;

	memset(dp, 0, sizeof(dp));
	for (int j = 1; j <= V; j++)
		dp[0][j] = -1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= V; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= v[i]&&dp[i][j-v[i]]!=-1)
				dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
		}
	}
	cout << (dp[n][V]==-1?0:dp[n][V]) << endl;
	return 0;
}
int coinChange(vector<int>& coins, int amount) {
	int n = coins.size();
	vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
	for (int j = 1; j <= amount; j++)
		dp[0][j] = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= amount; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= coins[i]&& dp[i][j - coins[i]]!=-1)
				dp[i][j] = min(dp[i][j], dp[i][j - coins[i]] + 1);
		}
	}
	return dp[n][amount]==0x3f3f3f3f?-1:dp[n][amount];
}
int change(int amount, vector<int>& coins) {
	int n = coins.size();
	vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
	for (int j = 1; j <= amount; j++)
		dp[0][j] = -1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= amount; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= coins[i]&& dp[i][j - coins[i]]!=-1)
				dp[i][j] += dp[i][j - coins[i]] + 1;
		}
	}
	return dp[n][amount];
}
int numSquares(int n) {
	int m = sqrt(n);
	vector<vector<int>> dp(m + 1, vector<int>(n + 1));
	for (int j = 1; j <= n; j++)
		dp[0][j] = 0x3f3f3f3f;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= i * i)
				dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
		}
	}
	return dp[m][n];
}
int findMaxForm(vector<string>& strs, int m, int n) {
	int l = strs.size();
	vector<vector<vector<int>>> dp(l + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
	for(int i=1;i<=l;i++)
		for(int j=1;j<=m;j++)
			for (int k = 1; k <= n; k++)
			{
				int a = 0, b = 0;
				for (auto& e : strs[i])
				{
					if (e == '0')
						a++;
					else
						b++;
				}
				dp[i][j][k] = dp[i - 1][j][k];
				if (j >= a && k >= b)
					dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
			}
	return dp[l][m][n];
}
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
	int m = group.size();
	vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
	for (int i = 0; i <= m; i++)
		for (int j = 0; j <= n; j++)
			dp[i][j][0] = 1;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			for (int k = 0; k <= minProfit; k++)
			{
				dp[i][j][k] = dp[i - 1][j][k];
				if (j >= group[i])
					dp[i][j][k] += dp[i - 1][j - group[i]][max(0, k - profit[i])];
			}
		}
	}
	return dp[m][n][minProfit];
}
//int _ret,_target,_n;
//void dfs(vector<int>& nums,int path)
//{
//	if (path == _target)
//	{
//		_ret++;
//		return;
//	}
//	if (path > _target)
//		return;
//	for (int i = 0; i < _n; i++)
//	{
//		dfs(nums, path + nums[i]);
//	}
//}
//int combinationSum4(vector<int>& nums, int target) {
//	_target = target,_n=nums.size();
//	dfs(nums, 0);
//	return _ret;
//}
int combinationSum4(vector<int>& nums, int target) {
	int n = nums.size();
	vector<int> dp(target + 1);
	dp[0] = 1;
	for (int i = 0; i < n; i++)
	{
		if(target>nums[i])
		dp[i] = dp[target - nums[i]];
	}
	return dp[target];
}
int numTrees(int n) {
	vector<int> dp(n + 1);
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = dp[i - 1] * dp[n - i];
	}
	return dp[n];
}